# k = 3
# n = 7
k = 3
n = 9
def combinationSum3(k: int, n: int):
    dictionary={1:False,2:False,3:False,4:False,5:False,6:False,7:False,8:False,9:False}
    ans=[]
    dfs([],ans,k,0,n,0,dictionary,1)
    print(ans)

def dfs(path,ans,k,curindex,n,curSum,dictionary,minFirst):
    #出口条件
    if curindex==k and curSum==n:
        if path not in ans:
            ans.append(path[:])
    for key in range(minFirst,10):
        if not dictionary[key]:
            #当前的元素还没有被使用
            if curSum+key>n:
                #这个path是行不通了
                return None
            path.append(key)
            dfs(path,ans,k,curindex+1,n,curSum+key,dictionary,key+1)
            #把刚加入的元素弹出，回溯状态
            path.pop()
combinationSum3(k,n)

